Applications often interact by exchanging messages. For example, a user interface application may interact with a Web service to query a database of products, update a description of a product, and save the updated description to the database. In this example, the order of the messages corresponding to the query, update, and save should be preserved when the messages are sent from the user interface to the database. To that end, reliable messaging mechanisms, such as WS-RM (see Web Services Reliable Messaging Protocol, February 2005, Rusian Bilorusets et al.), have been used to ensure that message delivery is guaranteed and, when necessary, delivered in a specified order. To provide reliable messaging, WS-RM specifies the protocol for message exchange including the retransmission of messages that are in error. To retransmit such messages, the sending and receiving application include a persistence mechanism (e.g., memory or storage) to store the message and a queue to maintain information concerning the order of a message relative to other messages. As a consequence, reliable messaging comes at the cost of increased processing requirements at the sender and receiver of the messages.